package org.example.Soution002;

import org.example.Soution001.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class StackWhichIsMin {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-10);
        minStack.push(14);
        System.out.println("2"+minStack.getMin());
        System.out.println("2"+minStack.getMin());
        minStack.push(-20);
        System.out.println("2"+minStack.getMin());
        System.out.println("2"+minStack.getMin());
        System.out.println("2"+minStack.top());
        System.out.println("2"+minStack.getMin());
        minStack.pop();
        System.out.println("1"+minStack.getMinPile());
        minStack.push(10);
        minStack.push(-7);
        System.out.println("2"+minStack.getMin());
        minStack.push(-7);
        minStack.pop();
        System.out.println("1"+minStack.getMinPile());
        System.out.println("2"+minStack.top());
//        minStack.push(0);
//        System.out.println("1"+minStack.getMinPile());
//        System.out.println("2"+minStack.getMin());
//        minStack.pop();
//        System.out.println("3"+minStack.getMinPile());
//        System.out.println("4"+minStack.getMin());
//        minStack.pop();
//        System.out.println("5"+minStack.getMinPile());
//        System.out.println("6"+minStack.getMin());
//        minStack.pop();
//        System.out.println("8"+minStack.getMin());
//        System.out.println("7"+minStack.getMinPile());
//        System.out.println("8"+minStack.getMin());
    }
}

class MinStack {
    private Stack<Integer> stack;
    private List<Integer> minPile ;

    public MinStack() {
        //初始化一个栈
        if(stack==null){
            stack=new Stack<>();
            minPile=new ArrayList<>();
        }
    }

    public void addElementAt(int val) {
        minPile.add(val);
        heapifyUp(minPile.size() - 1);
    }

    private void heapifyUp(int add){
        int son=add;
        int parent=(son-1)/2;
        while(son>0&&minPile.get(son)<minPile.get(parent)){
            swap(parent,son);
            son=parent;
            parent=(son-1)/2;
        }
    }

    List<Integer> getMinPile(){
        return minPile;
    }

    private void swap(int i,int j){
        int temp=minPile.get(i);
        minPile.set(i,minPile.get(j));
        minPile.set(j,temp);
    }


    public void push(int val) {
        addElementAt(val);
        stack.push(val);
    }

    private void removeElementAt(int index){
        int add= minPile.indexOf(index);
        if(add==-1) return;
        minPile.set(add,minPile.get(minPile.size()-1));
        minPile.remove(minPile.size()-1);
        if(add==0){
            heapifyDown(add);
        }else{
            if(add<minPile.size()){
                heapifyUp(add);
                heapifyDown(add);
            }
        }

    }

    private void heapifyDown(int val){
        int son=val,smallest = val;
        int grandsonL=son*2+1,grandsonR=son*2+2;
        if(grandsonL>=minPile.size()){
            return;
        }if(grandsonR>=minPile.size()){
            if(minPile.get(grandsonL)<minPile.get(son)){
                smallest=grandsonL;
            }
        }else{
            if(minPile.get(grandsonL)<=minPile.get(grandsonR)&&minPile.get(grandsonL)<minPile.get(son)){
                smallest=grandsonL;
            }
            if(minPile.get(grandsonR)<minPile.get(grandsonL)&&minPile.get(grandsonR)<minPile.get(son)){
                smallest=grandsonR;
            }
        }
        if(smallest!=son){
            swap(son,smallest);
            heapifyDown(smallest);
        }
    }

    public void pop() {
        int val = stack.pop();
        removeElementAt(val);
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minPile.get(0);
    }
}
